home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Windows Undocumented File Formats
/
Windows Undocumented File Formats.img
/
CHAP6
/
COMP.C
next >
Wrap
C/C++ Source or Header
|
1997-07-15
|
11KB
|
370 lines
/**********************************************************************
*
* PROGRAM: COMP.C
*
* PURPOSE: Compress a file using something like Microsoft's derivative on LZ77
* (i.e., it can be uncompressed using Microsoft's EXPAND.EXE)
*
* Copyright 1997, Mike Wallace and Pete Davis
*
* Chapter 6, Compression Algorithm and File Formats, from Undocumented Windows
* File Formats, published by R&D Books, an imprint of Miller Freeman, Inc.
*
**********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "decomp.h"
#define WINSIZE 4096
#define MAXLEN 18
#define COMP_CODE(x,y) ((((x-3) & 0x0F) << 8) + (((y - 0x10) & \
0x0F00) << 4) + ((y - 0x10) & 0x00FF))
#define LOBYTE(x) ((unsigned char)(x))
#define HIBYTE(x) ((unsigned char)(((unsigned short)(x) >> 8) & 0xFF))
#define DROP_INDEX(x) (x == 0) ? (WINSIZE - 1) : (x - 1)
#define ADD_INDEX(x) ((x + 1) == WINSIZE) ? 0 : (x + 1)
/* This is our Compression Window */
unsigned char Window[WINSIZE];
/***************************************************
Set bit number "bit" in byte "byte"
****************************************************/
void BitSet(int bit, char *byte)
{
short result = 1;
/* make sure bit range is 0,..,7 */
if (bit < 0) bit = 0;
else if (bit > 7) bit = 7;
while (bit--)
result *= 2;
*byte = result | *byte;
} /* BitSet - end */
/*************************************************
InBetween - detects if lower <= target <= higher
**************************************************/
int InBetween(int lower, int higher, int target)
{
if(higher < lower)
higher += WINSIZE;
if((lower <= target) && (target <= higher))
return 1;
else
return 0;
} /* InBetween - end */
/*************************************************
Force FlagByte and DataBytes to print out
**************************************************/
void WriteFlagByte(FILE *outfile)
{
int index = 0;
if(FlagCount > 0) {
DataBytes[DataCount] = '\0';
fputc(FlagByte, outfile);
for (; index < DataCount ; ++index)
fprintf(outfile, "%c", DataBytes[index]);
DataCount = FlagCount = 0;
FlagByte = '\0';
for (index = 0; index < 17; ++index)
DataBytes[index] = ' ';
}
} /* WriteFlagByte - end */
/*************************************************
Check if FlagByte is full and should be printed out
**************************************************/
void CheckFlagByte(FILE *outfile)
{
++DataCount;
if(++FlagCount == 8)
WriteFlagByte( outfile );
} /* CheckFlagByte - end */
/*************************************************
Saves an uncompressed data byte
**************************************************/
void GetNextChar( int *CurrPos, FILE *infile)
{
unsigned char ch;
fread(&ch, sizeof(char), 1, infile);
if (!feof(infile))
Window[*CurrPos = ADD_INDEX(*CurrPos)] = ch;
} /* GetNextChar - end */
/*************************************************
Unreads the last character read
**************************************************/
void UnreadChar(unsigned char ch, FILE *infile, int *CurrPos,
unsigned char ch2)
{
ungetc( ch, infile);
Window[*CurrPos] = ch2;
*CurrPos = DROP_INDEX(*CurrPos);
} /* UnreadChar - end */
/*************************************************
Saves an uncompressed data byte
**************************************************/
void SaveUncompByte(unsigned char ch, FILE *outfile)
{
BitSet(FlagCount, &FlagByte);
DataBytes[DataCount] = ch;
CheckFlagByte( outfile );
} /* SaveUncompByte - end */
/*************************************************
Compresses the data using Microsoft's LZ77
derivative (Zeck).
**************************************************/
void Compress(FILE *infile, FILE *outfile)
{
int count=0, shifter=0, CurrPos=0;
int SavePos=0, iCompCode = 0, offset = 0;
int newPos = 0;
unsigned char ch;
int bestcount = 0, bestoffset = 0;
char oldchars[3];
FlagCount = 0;
DataCount = 0;
FlagByte = '\0';
for (count = 0; count < WINSIZE; count ++)
Window[count] = ' ';
rewind( infile );
/* Go through input file until we're done */
fread(&ch, sizeof(char), 1, infile);
Window[CurrPos] = ch;
while (!feof(infile)) {
/* if less than 3 chars from end, just write out remainder */
if((InfileSize - ftell(infile)) < 2) {
SaveUncompByte( Window[CurrPos], outfile);
GetNextChar( &CurrPos, infile);
continue;
}
/* Find previous occurrence of character in window */
for (count = 1, shifter = DROP_INDEX(CurrPos);
(Window[shifter] != Window[CurrPos]) && (count < WINSIZE);
++count, shifter = DROP_INDEX(shifter)) {}
/* check if char is unique so far in input file */
if(count == WINSIZE) {
SaveUncompByte( Window[CurrPos], outfile);
GetNextChar( &CurrPos, infile);
continue;
}
else {
/* find out how many characters match */
SavePos = CurrPos;
oldchars[2] = oldchars[0] = Window[ADD_INDEX(CurrPos)];
GetNextChar( &CurrPos, infile);
for(count = 1, offset=shifter, shifter = ADD_INDEX(shifter);
(!feof(infile)) && (Window[shifter] == Window[CurrPos]) &&
(count < MAXLEN);) {
++count;
if(count == 2)
oldchars[1] = Window[ADD_INDEX(CurrPos)];
oldchars[2] = Window[ADD_INDEX(CurrPos)];
GetNextChar( &CurrPos, infile);
shifter = ADD_INDEX(shifter);
}
/* Since this is the first match, save it as the best so far */
bestcount = count;
bestoffset = offset;
if(((Window[shifter] != Window[CurrPos]) || (count == MAXLEN)) &&
(!feof(infile)))
UnreadChar( Window[CurrPos], infile, &CurrPos, oldchars[2]);
/* Now find the best match for the string in the window */
shifter = DROP_INDEX( offset );
while((shifter != CurrPos) && (bestcount < MAXLEN) &&
(!InBetween( SavePos, CurrPos, shifter))) {
for( ; (shifter != CurrPos) && (Window[shifter] != Window[SavePos]);
shifter = DROP_INDEX(shifter)) {}
if(shifter == CurrPos)
continue;
for(count = 0, offset = shifter, newPos = SavePos;
(!feof(infile)) && (Window[shifter] == Window[newPos]) &&
(count < MAXLEN); ++count, newPos = ADD_INDEX(newPos)) {
if (count >= (bestcount - 1)) {
if(count == 1)
oldchars[1] = Window[ADD_INDEX(CurrPos)];
oldchars[2] = Window[ADD_INDEX(CurrPos)];
GetNextChar( &CurrPos, infile );
}
shifter = ADD_INDEX(shifter);
}
if(((count >= MAXLEN) || ((Window[shifter] != Window[newPos]) &&
(count >= bestcount))) && (!feof(infile)))
UnreadChar( Window[CurrPos], infile, &CurrPos, oldchars[2]);
if(count > bestcount) {
bestcount = count;
bestoffset = offset;
}
shifter = DROP_INDEX( offset );
} /* while(shifter != CurrPos) */
if(!feof(infile))
GetNextChar( &CurrPos, infile );
count = bestcount;
offset = bestoffset;
/* if count < 3, then not enough chars to compress */
if (count < 3) {
SaveUncompByte( Window[SavePos], outfile);
fseek(infile, ftell(infile) - count, 0);
Window[SavePos = ADD_INDEX(SavePos)] = oldchars[0];
CurrPos = DROP_INDEX(CurrPos);
if (count == 2) {
Window[ADD_INDEX(SavePos)] = oldchars[1];
CurrPos = DROP_INDEX(CurrPos);
}
}
else {
iCompCode = COMP_CODE(count, offset);
DataBytes[DataCount] = LOBYTE(iCompCode);
DataBytes[++DataCount] = HIBYTE(iCompCode);
CheckFlagByte( outfile );
if (!feof(infile))
UnreadChar( Window[CurrPos], infile, &CurrPos, oldchars[2]);
}
if((!feof(infile)) && (count <= MAXLEN))
GetNextChar( &CurrPos, infile);
}
} /* while - end */
WriteFlagByte( outfile );
} /* Compress - end */
/***************************************************
Write the header that exists at the beginning of
every file compressed using MS's Zeck compression
****************************************************/
void WriteHeader(FILE *infile, FILE *outfile)
{
COMPHEADER CompHeader;
CompHeader.Magic1 = MAGIC1;
CompHeader.Magic2 = MAGIC2;
CompHeader.Is41 = 0x41;
CompHeader.FileFix = '\0'; /* This stores the original last */
/* char. of the input filename */
fseek( infile, 0L, 2);
CompHeader.DecompSize = InfileSize = ftell(infile);
rewind( infile );
rewind( outfile);
fwrite(&CompHeader, sizeof(CompHeader), 1, outfile);
Compress(infile, outfile);
} /* WriteHeader - end */
/***************************************************
Show usage.
****************************************************/
void Usage( void )
{
printf("Usage:\n");
printf(" COMP file1.ext file2.ext\n\n");
printf(" file1.ext - Name of uncompressed file\n");
printf(" file2.ext - Name of compressed file\n\n");
} /* Usage - end */
/***************************************************
Open the input and output files, and call routine
to compress the data.
****************************************************/
int main(int argc, char *argv[])
{
char filename[128];
FILE *infile, *outfile;
if (argc != 3) {
Usage();
return EXIT_FAILURE;
}
strcpy(filename, argv[1]);
if ((infile = fopen(filename, "rb")) == NULL) {
printf("%s does not exist\n", filename);
return(EXIT_FAILURE);
}
strcpy(filename, argv[2]);
if ((outfile=fopen(filename, "wb+")) == NULL) {
printf("Error opening destination file\n");
return(EXIT_FAILURE);
}
WriteHeader(infile, outfile);
fclose(infile);
fclose(outfile);
return(EXIT_SUCCESS);
} /* main - end */
/* comp.c - end */